/**
**********************************************************************
*   Copyright (C) 2021 wy1107412334@163.com All rights reserved.
*
* @file     double_link_list.c
* @brief    对文件的简要说明
* @details  对文件的详细说明
* @author   jcai
* @Version  v0.0.1
* @date     2021-05-17 15:27:15
*
*   Email:  wy1107412334@163.com
*   Blog:   None
*   Github: https://github.com/wy1107412334
*   Gitee:  https://gitee.com/git.git1107412334.com
*
**********************************************************************
@verbatim

空链表
=====

链表头：
+------+------+
| head | NULL |
+------+------+
| tail | NULL |
+------+------+


存在一个节点的链表
=================

链表头：               节点
+------+         +---->+------+------+
| head |---------+     | prev | NULL |
+------+         |     +------+------+
| tail |---------+     | next | NULL |
+------+               +------+------+


存在两个节点的链表
=================

                 +------------------------------------+
                 |                                    |
链表头：         |     节点1                节点2     |
+------+         +---> +------+------+ +--> +------+  |
| head |---------+     | prev | NULL | |    | prev |--+
+------+               +------+------+ |    +------+------+
| tail |---------+     | next |--------+    | next | NULL |
+------+         |     +------+        |    +------+------+
                 +---------------------+


存在三个节点的链表
=================

                                       +-------------------------------+
                 +------------------------------------+                |
                 |                     |              |                |
链表头：         |     节点1           |    节点2     |      节点3     |
+------+         +---> +------+------+ +--> +------+  | +--> +------+  |
| head |>--------+     | prev | NULL | |    | prev |>-+ |    | prev |>-+
+------+               +------+------+ |    +------+    |    +------+------+
| tail |>--------+     | next |>-------+    | next |>---+    | next | NULL |
+------+         |     +------+             +------+    |    +------+------+
                 +--------------------------------------+


使用链表节点的数据类型
=====================

struct abc {
    DL_NODE    node;
    int        val;
};

                                       +-------------------------------+
                 +------------------------------------+                |
                 |                     |              |                |
链表头：         |     节点1           |    节点2     |      节点3     |
+------+         +---> +------+------+ +--> +------+  | +--> +------+  |
| head |>--------+     | prev | NULL | |    | prev |>-+ |    | prev |>-+
+------+               +------+------+ |    +------+    |    +------+------+
| tail |>--------+     | next |>-------+    | next |>---+    | next | NULL |
+------+         |     +------+             +------+    |    +------+------+
                 |     | val  |             | val  |    |    | val  |
                 |     +------+             +------+    |    +------+
                 +--------------------------------------+

@endverbatim
**********************************************************************
* @note
* None.
**********************************************************************
* @attention
*
* 链表简介
* =======
*
* 1. 本链表是一个双向链表。
*   - 从链表头节点向后指，可以一直指到尾节点。任何非尾节点都可以向后指，
*     可以一直指到尾结点。
*   - 从链表尾节点向前指，可以一直指到头节点。任何非头节点都可以向前指，
*     可以一直指到头节点。
* 2. 本链表有一个链表表头和若干个链表节点。
*   - 链表表头用于表示一个链表。其中保存了链表的头节点和尾节点的地址。
*   - 每个节点中有 prev 和 next 这两个元素
* 3. 空链表的表头的 head 和 tail 元素的值为 NULL。
* 4. 非空链表的尾节点的 next 元素的值为 NULL。
* 5. 非空链表的头结点的 prev 元素的值为 NULL。
*
*
* 链表使用
* =======
* 1. 数据类型 DL_NODE 需要放在用户自定义的struct的最开头，
*    这样链表节点的地址也就是用户自定义的struct的首地址。
*    这样方便通过本链表返回的节点地址来处理用户自定义的数据。
*    <code c>
*    struct abc {
*        DL_NODE node;
*        // 用户定义的数据类型字段
*    };
*    </code>
* 2. 先创建并初始化一个链表的表头，可以使用如下两种方式：
*   - 定义 DL_LIST 类型变量，然后将变量的地址传递给函数 dllist_static_init
*   - 定义 DL_LIST * 类型变量保存函数 dllist_alloc_init 的返回值
* 3. 对上面初始化的链表进行操作。
*
**********************************************************************
* @par 历史记录
*  1. V0.0.1: jcai, 2021-05-17 15:27:15
*    - 首次编写
*  2. V0.0.2: jcai, 2021年5月18日 20点39分
*    - 新增三个函数
*    - 编写文件头注释
*  3. V0.0.3: jcai, 2021年5月19日 19点07分
*    - 修改寻找链表中指定节点的函数及其回调函数的参数表
*  4. V0.0.4: jcai, 2021年5月24日 18点41分
*    - 新增函数：dllist_deleteAt()
*    - 使用枚举值替换函数返回的错误码
*
**********************************************************************
*/

/* 头文件导入区 --------------------------------------------------- */

#include <stdlib.h>
#include "double_link_list.h"


/** @defgroup DOUBLE_LINK_LIST DOUBLE_LINK_LIST
* @brief double link list modules
* @{
*/



/*********************************************************************
                私有宏定义
*********************************************************************/






/*********************************************************************
                私有数据类型声明
*********************************************************************/








/*********************************************************************
                私有变量定义
*********************************************************************/





/** @defgroup DOUBLE_LINK_LIST_Exported_Variables double link list exported variables
* @brief 全局变量定义
* @{
*/



/** defgroup DOUBLE_LINK_LIST_Exported_Variables
* @}
*/





/*********************************************************************
                私有函数定义
*********************************************************************/









/** @defgroup DOUBLE_LINK_LIST_Exported_Functions double link list exported functions
* @brief 全局函数定义
* @{
*/



/**
**********************************************************************
* @brief    初始化链表
* @details  初始化链表
* @param[out] dl: 指向链表头的指针
* @retval  None.
* @note    None.
* @par 历史记录
*  1. V0.0.1: jcai, 2021-05-17 15:27:15
*    - 首次编写
*/
void dllist_static_init(DL_LIST *dl)
{
    if (dl)
    {
        dl->head = NULL;
        dl->tail = NULL;
    }
}

/**
**********************************************************************
* @brief    动态申请并初始化链表头
* @details  本函数先动态申请一块保存链表头的内存空间，
*           然后初始化该链表，最后返回链表头的地址。
* @param   None.
* @return  成功，返回已初始化的链表头的地址；失败，返回NULL
* @note    在不使用本函数创建的链表时，需要调用函数 dllist_free()
*          来释放链表头占用的空间；或者说也可以直接调用函数 free()
*          来释放本函数创建的链表头占用的内存空间。
* @par 历史记录
*  1. V0.0.1: caijing，2021-05-11 09:23:28
*    - 首次编写
*/
DL_LIST *dllist_alloc_init(void)
{
    DL_LIST *p = (DL_LIST *)malloc(sizeof(DL_LIST));
    dllist_static_init(p);
    return p;
}

/**
**********************************************************************
* @brief   释放动态申请的链表头
* @details 释放动态申请的链表头
* @param [in] dl: 指向链表头的指针
* @retval 0  成功
* @retval DL_ERR_ARGS 参数 dl 为NULL
* @retval DL_ERR_NOTEMPTY 链表 dl 非空
* @note    在使用函数 dllist_alloc_init() 返回的链表头指针，
*          需要调用本函数来释放链表头占用的空间；
*          或者说也可以直接调用函数 free() 来释放函数
*          dllist_alloc_init() 创建的链表头占用的内存空间。
*          如果链表 dl 为非空，那么将返回-2
* @par 历史记录
*  1. V0.0.1: caijing，2021-05-11 09:23:28
*    - 首次编写
*/
int32_t dllist_free(const DL_LIST *dl)
{
    if (!dl)        return DL_ERR_ARGS;
    if (dl->head)   return DL_ERR_NOTEMPTY;
    free((void *)dl);
    return 0;
}

/**
**********************************************************************
* @brief   销毁链表
* @details 释放链表 dl 中的所有节点
* @param [in,out] dl: 指向链表头的指针
* @return  None.
* @note    链表 dl 中的所有节点必须都是动态申请的。
*          本函数执行完成之后，链表 dl 就是一个空链表了。
*          如果本链表中的节点的地址不是动态申请的内存的首地址，
*          那么请使用函数 dllist_destroyCallback() 来进行内存释放。
* @par 历史记录
*  1. V0.0.1: jcai, 2021年5月16日 21点31分
*    - 首次编写
*/
void dllist_destroy(DL_LIST *dl)
{
    DL_NODE *pNode;
    DL_NODE *tmp;

    if (!dl)    return;

    for (pNode = dl->head; pNode; pNode = tmp)
    {
        tmp = pNode->next;
        free((void *)pNode);
    }
    dl->head = dl->tail = NULL;
}

/**
**********************************************************************
* @brief   销毁链表
* @details 使用回调函数 callback 来释放链表 dl 中的所有节点
* @param [in,out] dl: 指向链表头的指针
* @param [in] callback: 指向释放链表中所有节点的函数的指针
* @retval DL_ERR_ARGS: 参数 dl 或 callback 为 NULL
* #retval 0: 成功
* @note    本函数执行完成之后，链表 dl 就是一个空链表了。
* @par 历史记录
*  1. V0.0.1: jcai, 2021年5月16日 21点31分
*    - 首次编写
*/
int32_t dllist_destroyCallback(DL_LIST *dl, dl_trav_callback callback)
{
    DL_NODE *pNode;
    DL_NODE *tmp;

    if (!dl || !callback)    return DL_ERR_ARGS;

    for (pNode = dl->head; pNode; pNode = tmp)
    {
        tmp = pNode->next;
        callback(pNode);
    }
    dl->head = dl->tail = NULL;
    return 0;
}

/**
**********************************************************************
* @brief    链表是否为空
* @details  链表是否为空
* @param[in] dl: 指向链表头的指针
* @retval DL_ERR_ARGS 参数 dl 为NULL
* @retval  0 链表不为空
* @retval  1 链表为空
* @note    None.
* @par 历史记录
*  1. V0.0.1: jcai, 2021-05-17 15:27:15
*    - 首次编写
*/
int32_t dllist_isempty(const DL_LIST *dl)
{
    if (!dl)    return DL_ERR_ARGS;

    if (dl->head)   return 0;

    return 1;
}

/**
**********************************************************************
* @brief    返回链表长度
* @details  返回链表中节点的数量
* @param[in] dl: 指向链表头的指针
* @return  返回非负值，是链表长度；返回 DL_ERR_ARGS ，参数 dl 为NULL
* @note    None.
* @par 历史记录
*  1. V0.0.1: jcai, 2021-05-17 15:27:15
*    - 首次编写
*/
int32_t dllist_length(const DL_LIST *dl)
{
    DL_NODE *pNode;
    int32_t  len = 0;

    if (!dl)    return DL_ERR_ARGS;

    DL_FOREACH(pNode, dl, DOWN)
        len++;

    return len;
}

/**
**********************************************************************
* @brief    插入一个节点到链表头节点
* @details  将节点 node  插入到链表 dl 中作为头节点
* @param[in,out] dl: 指向链表头的指针
* @param[in,out] node: 指向节点的指针
* @retval DL_ERR_ARGS 参数 dl 或 node 为NULL
* @retval DL_ERR_ISEXIST 链表 dl 中存在节点 node
* @retval  0 成功
* @note    None.
* @par 历史记录
*  1. V0.0.1: jcai, 2021-05-17 15:27:15
*    - 首次编写
*/
int32_t dllist_insert_head(DL_LIST *dl, DL_NODE *node)
{
    if (!dl || !node)   return DL_ERR_ARGS;

    if (dllist_addr2at(dl, node) >= 0)   return DL_ERR_ISEXIST;

    node->next = dl->head;
    node->prev = NULL;
    if (dl->head)
        dl->head->prev = node;
    dl->head = node;
    if (!dl->tail)
        dl->tail = node;

    return 0;
}

/**
**********************************************************************
* @brief    在链表指定节点之后插入节点
* @details  将节点 node 插入到链表 dl 中第 index 个节点之后。
* @param[in,out] dl: 指向链表头的指针
* @param[in,out] node: 指向节点的指针
* @param[in]     index: 链表中第index个节点，从0开始；
*                       范围：0 ~ 链表 dl 长度 - 1
* @retval DL_ERR_ARGS 参数 dl 或 node 为NULL
* @retval DL_ERR_ISEXIST 链表 dl 中存在节点 node
* @retval DL_ERR_INDEX 参数 index 大于等于链表 dl 的长度
* @retval  0 成功
* @note    如果链表 dl 是一个空链表，那么本函数将返回 DL_ERR_INDEX
* @par 历史记录
*  1. V0.0.1: jcai, 2021-05-17 15:27:15
*    - 首次编写
*/
int32_t dllist_insert_at(DL_LIST *dl, DL_NODE *node, uint32_t index)
{
    DL_NODE *pNode;
    uint32_t i;

    if (!dl || !node)   return DL_ERR_ARGS;

    if (dllist_addr2at(dl, node) >= 0)   return DL_ERR_ISEXIST;

    for (pNode = dl->head, i = 0;
         pNode && (i < index);
         pNode = pNode->next, i++) ;

    if (!pNode)         return DL_ERR_INDEX;

    if (dl->tail == pNode)
        dl->tail = node;
    else
        pNode->next->prev = node;
    node->prev = pNode;
    node->next = pNode->next;
    pNode->next = node;

    return 0;
}

/**
**********************************************************************
* @brief    插入一个节点到链表尾节点
* @details  将节点 node 插入到链表 dl 中作为尾节点
* @param[in,out] dl: 指向链表头的指针
* @param[in,out] node: 指向节点的指针
* @retval DL_ERR_ARGS 参数 dl 或 node 为NULL
* @retval DL_ERR_ISEXIST 链表 dl 中存在节点 node
* @retval  0 成功
* @note    None.
* @par 历史记录
*  1. V0.0.1: jcai, 2021-05-17 15:27:15
*    - 首次编写
*/
int32_t dllist_insert_tail(DL_LIST *dl, DL_NODE *node)
{
    if (!dl || !node)    return DL_ERR_ARGS;

    if (dllist_addr2at(dl, node) >= 0)   return DL_ERR_ISEXIST;

    node->next = NULL;
    if (dl->tail)
    {
        dl->tail->next = node;
        node->prev     = dl->tail;
        dl->tail       = node;
    }
    else
    {
        node->prev = node->next;
        dl->head   = node;
        dl->tail   = node;
    }

    return 0;
}

/**
**********************************************************************
* @brief    获取链表中指定节点的地址
* @details  获取链表 dl 中第 index 个节点的地址。index的值从0开始
* @param[in] dl: 指向链表头的指针
* @param[in] index: 链表中第index个节点，从0开始；
*                   范围：0 ~ 链表 dl 长度 - 1
* @return 返回非NULL，成功；否则失败。
* @note   None.
* @par 历史记录
*  1. V0.0.1: jcai, 2021-05-17 15:27:15
*    - 首次编写
*/
DL_NODE *dllist_at(const DL_LIST *dl, uint32_t index)
{
    DL_NODE *pNode;
    uint32_t i;

    if (!dl)    return NULL;

    for (pNode = dl->head, i = 0; pNode; pNode = pNode->next, i++)
    {
        if (i == index)
            return pNode;
    }
    return NULL;
}

/**
**********************************************************************
* @brief    获取传入节点在链表中是第几个节点
* @details  返回传入节点 node 是链表 dl 中的第几个节点。
* @param[in] dl: 指向链表头的指针
* @param[in] node: 指向节点的指针
* @return   返回非负数，成功；否则失败
* @note   None.
* @par 历史记录
*  1. V0.0.1: jcai, 2021-05-17 15:27:15
*    - 首次编写
*/
int32_t dllist_addr2at(const DL_LIST *dl, const DL_NODE *node)
{
    const DL_NODE *pNode;
    int32_t i;

    if (!dl || !node)   return DL_ERR_ARGS;

    for (pNode = dl->head, i = 0; pNode; pNode = pNode->next, i++)
    {
        if (pNode == node)
            return i;
    }
    return DL_ERR_NOTEXIST;
}

/**
**********************************************************************
* @brief    删除一个节点
* @details  删除链表 dl 中节点地址为 node 的节点
* @param[in,out] dl: 指向链表头的指针
* @param[in] node: 指向节点的指针
* @retval DL_ERR_ARGS 参数 dl 或 node 为 NULL
* @retval DL_ERR_NOTEXIST 链表 dl 中不存在 node 指向的节点
* @retval  0 删除成功
* @note    None.
* @par 历史记录
*  1. V0.0.1: jcai, 2021-05-17 15:27:15
*    - 首次编写
*/
int32_t dllist_delete(DL_LIST *dl, const DL_NODE *node)
{
    DL_NODE *pNode;
    int32_t ret = DL_ERR_ARGS;

    if (!dl || !node)   return ret;

    ret = DL_ERR_NOTEXIST;
    if (!dl->head)      goto return_point;

    pNode = dl->head;
    if (pNode == node)
    {
        if (dl->head == dl->tail)
            dl->tail = dl->tail->next;
        dl->head = dl->head->prev;
        ret = 0;
        goto return_point;
    }

    while (pNode->next)
    {
        if (pNode->next == node)
        {
            if (pNode->next == dl->tail)
                dl->tail = pNode;
            pNode->next = pNode->next->next;
            ret = 0;
            goto return_point;
        }

        pNode = pNode->next;
    }

return_point:
    return ret;
}

/**
**********************************************************************
* @brief    删除链表中指定节点
* @details  删除链表 dl 中第 index 个节点。index的值从0开始
* @param[in,out] dl: 指向链表头的指针
* @param[in] index: 链表中第index个节点，从0开始；
*                   范围：0 ~ 链表 dl 长度 - 1
* @return 失败，返回NULL；否则返回被删除的节点的首地址。
* @note   None.
* @par 历史记录
*  1. V0.0.1: jcai, 2021年5月24日 17点54分
*    - 首次编写
*/
DL_NODE * dllist_deleteAt(DL_LIST *dl, uint32_t index)
{
    DL_NODE *pNode;
    uint32_t i;

    if (!dl)    return NULL;

    for (pNode = dl->head, i = 0; pNode; pNode = pNode->next, i++)
    {
        if (i == index)
        {
            if (!pNode->prev)
            {
                dl->head = pNode->next;
                if (pNode->next)
                    pNode->next->prev = pNode->prev;    // NULL
            }
            else
                pNode->prev->next = pNode->next;

            if (!pNode->next)
            {
                dl->tail = pNode->prev;
                if (pNode->prev)
                    pNode->prev->next = pNode->next;    // NULL
            }
            else
                pNode->next->prev = pNode->prev;

            return pNode;
        }
    }
    return NULL;
}

/**
**********************************************************************
* @brief    遍历链表
* @details  将链表 dl 中的所有节点的地址作为参数调用函数 callback
* @param[in] dl: 指向链表头的指针
* @param[in] callback: 指向遍历节点的函数的指针
* @return  返回0，遍历成功；返回DL_ERR_ARGS，参数 dl 或 callback 为NULL
* @note    None.
* @par 历史记录
*  1. V0.0.1: jcai, 2021-05-17 15:27:15
*    - 首次编写
*/
int32_t dllist_traverse(const DL_LIST *dl, dl_trav_callback callback)
{
    const DL_NODE *pNode;

    if (!dl || !callback)   return DL_ERR_ARGS;

    DL_FOREACH(pNode, dl, DOWN)
    {
        callback(pNode);
    }
    return 0;
}

/**
**********************************************************************
* @brief    链表排序
* @details  回调函数 callback 用于控制本函数对链表 dl 进行升序或者降序排序。
* @param[in,out] dl: 指向链表头的指针
* @param[in] callback: 指向控制排序方式的函数的指针
* @return  返回0，排序成功；返回DL_ERR_ARGS，参数 dl 或 callback 为NULL
* @note    None.
* @par 历史记录
*  1. V0.0.1: jcai, 2021-05-17 15:27:15
*    - 首次编写
*/
int32_t dllist_sort(DL_LIST *dl, dl_sort_callback callback)
{
    DL_NODE *pNode1;
    DL_NODE *pNode2;
    DL_NODE *tmp, *prev, *next;

    if (!dl || !callback)       return DL_ERR_ARGS;
    if (dl->head == dl->tail)   return 0;

    for (pNode1 = dl->head;
         pNode1 && pNode1->next;
         pNode1 = pNode1->next)
    {
        for (pNode2 = pNode1->next; pNode2; pNode2 = pNode2->next)
        {
            if (callback((const DL_NODE *)pNode1, (const DL_NODE *)pNode2))
            {
                if (pNode1 == dl->head)
                    dl->head = pNode2;
                if (pNode2 == dl->tail)
                    dl->tail = pNode1;

                if (pNode1->prev)
                    pNode1->prev->next = pNode2;
                if (pNode2->next)
                    pNode2->next->prev = pNode1;

                if (pNode1->next == pNode2)
                {
                    prev = pNode2;
                    next = pNode1;
                }
                else
                {
                    pNode2->prev->next = pNode1;
                    pNode1->next->prev = pNode2;

                    prev = pNode2->prev;
                    next = pNode1->next;
                }

                pNode2->prev = pNode1->prev;
                pNode1->next = pNode2->next;
                pNode1->prev = prev;
                pNode2->next = next;

                tmp = pNode2;
                pNode1 = pNode2;
                pNode2 = tmp;
            }
        }
    }

    return 0;
}

/**
**********************************************************************
* @brief    寻找链表中指定节点
* @details  如果找到了指定节点，那么 callback 返回非0值
* @param[in] dl: 指向链表头的指针
* @param[in] callback: 指向寻找指定节点的函数的指针
* @param[in] arg: 回调函数 callback 的第二个参数
* @return  返回非NULL，成功；否则失败
* @note    None.
* @par 历史记录
*  1. V0.0.1: jcai, 2021-05-17 15:27:15
*    - 首次编写
*  2. V0.0.2: jcai, 2021年5月19日 19点07分
*    - 新增一个参数，用于传递一个用户参数给回调函数
*/
DL_NODE *dllist_find(const DL_LIST *dl, dl_match_callback callback, void *arg)
{
    DL_NODE *pNode;

    if (!dl || !callback)   return NULL;

    DL_FOREACH(pNode, dl, UP)
    {
        if (callback((const DL_NODE *)pNode, arg))
            return pNode;
    }
    return NULL;
}


/** defgroup DOUBLE_LINK_LIST_Exported_Functions
* @}
*/

/** defgroup DOUBLE_LINK_LIST
* @}
*/


/***  Copyright (C) 2021 wy1107412334@163.com All rights reserved ***/
/****************************** END OF FILE *************************/

